//Given an array of non-negative integers nums, you are initially positioned at
//the first index of the array. 
//
// Each element in the array represents your maximum jump length at that positio
//n. 
//
// Determine if you are able to reach the last index. 
//
// 
// Example 1: 
//
// 
//Input: nums = [2,3,1,1,4]
//Output: true
//Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
// 
//
// Example 2: 
//
// 
//Input: nums = [3,2,1,0,4]
//Output: false
//Explanation: You will always arrive at index 3 no matter what. Its maximum jum
//p length is 0, which makes it impossible to reach the last index.
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 3 * 104 
// 0 <= nums[i] <= 105 
// 
// Related Topics 贪心算法 数组 
// 👍 1189 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Jump Game
class P55JumpGame {
    public static void main(String[] args) {
        Solution solution = new P55JumpGame().new Solution();
        // TO TEST
        Assert.assertEquals(solution.canJump(new int[]{3,2,1,0,4}), false);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //1.动态规划
        public boolean canJump(int[] nums) {
            int lastIndex = nums.length - 1;
            int jump = 0;
            if (nums.length == 1) {
                return true;
            }
            if (nums[0] == 0) {
                return false;
            }
            for (int i = 0; i < nums.length - 1; i++) {
                if (jump >= i) {
                    jump = Math.max(jump, i + nums[i]);
                }
                if (jump >= lastIndex) {
                    return true;
                }
            }
            return false;
        }
        //2.递归超时
        public boolean canJumpRec(int[] nums) {
            int lastIndex = nums.length - 1;
            return canJump(0, lastIndex, nums);
        }

        private boolean canJump(int i, int lastIndex, int[] nums) {
            if (lastIndex == 0) {
                return true;
            }
            if (lastIndex < 0) {
                return false;
            }
            boolean flag = false;
            for (int j = 1; j <= nums[i]; j++) {
                flag = flag || canJump(i + j, lastIndex - j, nums);
            }
            return flag;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}